package AVLTree.method;

import AVLTree.pojo.AVLTree;

import java.util.Scanner;

/**
 * <p>
 * AVL树的增删改查操作
 * AVL是对二叉排序树的优化，在一定程度上有效解决了二叉排序树容易退化成链表的缺陷
 * 但同时AVL本身并不完美，高度差>1就需要进行旋转使得它的旋转过于频繁
 * 笔者认为，它是一种对二叉排序树和红黑树的承上启下
 * 理解好AVL树，既能让我们更加理解二叉排序树，又能为我们后面红黑树的学习一定程度上提供借鉴和思考
 * </p>
 *
 * @author 没天赋
 * @since 2025-03-10
 */
public class crud {
    static int n, m, k;
    static AVLTree root;
    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        //1.输入要插入几个值
        n = sc.nextInt();
        //2.依次插入
        for (int i = 0; i < n; i++) {
            int val = sc.nextInt();
            root = insert(root, val);
        }
        inOrder(root);
        //3.输入要进行几次删除操作
        m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            k = sc.nextInt();
            root = delete(root, k);
            inOrder(root);
        }
    }

    /**
     * 删除节点
     *
     * @param root
     * @param k
     * @return root
     */
    public static AVLTree delete(AVLTree root, int k) {
        if (root == null) {
            return null;
        }
        // 1.判断往哪个方向删除
        if (k < root.getVal()) {
            // 1.1. k<当前节点值则向左继续删除
            root.setLeft(delete(root.getLeft(), k));
            //对于平衡性来说，向左删除节点相当于向右插入节点
            if (safeHeight(root.getRight()) - safeHeight(root.getLeft()) > 1) {
                AVLTree right = root.getRight();
                //特别注意，当左右子树高度相同时，这里仍然认为是RR
                if (safeHeight(right.getRight()) >= safeHeight(right.getLeft())) {
                    // RR
                    root = rr_rotate(root);
                } else {
                    // RL
                    root = rl_rotate(root);
                }
            }
        } else if (k > root.getVal()) {
            // 1.2. k>当前节点值则向右继续删除
            root.setRight(delete(root.getRight(), k));
            //对于平衡性来说，向右删除节点相当于向左插入节点
            if (safeHeight(root.getLeft()) - safeHeight(root.getRight()) > 1) {
                AVLTree left = root.getLeft();
                //特别注意，当左右子树高度相同时，这里仍然认为是LL
                if (safeHeight(left.getLeft()) >= safeHeight(left.getRight())) {
                    // LL
                    root = ll_rotate(root);
                } else {
                    // LR
                    root = lr_rotate(root);
                }
            }
        } else {
            // 1.3. 删除本节点
            if (root.getLeft() != null && root.getRight() != null) {
                // 如果本节点度为2,将左子树最大值替代本节点
                // 1.3.1 本节点值改为左子树最大值
                AVLTree pre = get_pre(root.getLeft());
                root.setVal(pre.getVal());
                // 1.3.2 删除左子树最大值
                root.setLeft(delete(root.getLeft(), pre.getVal()));

                //这里因为删除了左子树的节点所以和上面的操作相同
                //对于平衡性来说，向左删除节点相当于向右插入节点
                if (safeHeight(root.getRight()) - safeHeight(root.getLeft()) > 1) {
                    AVLTree right = root.getRight();
                    //特别注意，当左右子树高度相同时，这里仍然认为是RR
                    if (safeHeight(right.getRight()) >= safeHeight(right.getLeft())) {
                        // RR
                        root = rr_rotate(root);
                    } else {
                        // RL
                        root = rl_rotate(root);
                    }
                }
            } else if (root.getLeft() != null) {
                //如果度为1且左子树存在
                root = root.getLeft();
            } else {
                //如果度为1且右子树存在或度为0
                root = root.getRight();
            }
        }
        // 2.更新高度
        if (root != null) { // 添加判空保护
            root.setH(root.getHeight());
        }
        return root;
    }

    /**
     * 获得中序遍历的前驱节点，也就是左子树最大值
     *
     * @param root
     * @return
     */
    public static AVLTree get_pre(AVLTree root) {
        return root.getRight() == null ? root : get_pre(root.getRight());
    }

    /**
     * 插入节点值（插入原理与二叉排序树相同）
     * 分为ll，lr，rr，rl四种旋转情况
     *
     * @param root
     * @param val
     * @return root
     */
    public static AVLTree insert(AVLTree root, int val) {
        //先判断是否为null
        if (root == null) {
            root = new AVLTree(val, 1, null, null);
            return root;
        }

        //1.插入
        //如果插入值小于root的值向左递归
        if (val < root.getVal()) {
            root.setLeft(insert(root.getLeft(), val));

            //获取左右子树高度
            int lh = safeHeight(root.getLeft());
            int rh = safeHeight(root.getRight());//注意右子树可能为null

            //2.判断是否需要旋转
            //如果高度差>2且插入在左子树的左边则满足ll的情况
            if (lh - rh > 1) {
                if (val < root.getLeft().getVal()) {
                    root = ll_rotate(root);
                } else {//否则插在左子树的右边满足lr的情况
                    root = lr_rotate(root);
                }
            }
        } else {//如果插入值大于root的值向右递归
            root.setRight(insert(root.getRight(), val));

            //获取左右子树高度
            int lh = safeHeight(root.getLeft());//注意左子树可能为null
            int rh = safeHeight(root.getRight());

            //如果高度差>2且插入在左子树的左边则满足ll的情况
            if (rh - lh > 1) {
                if (val > root.getRight().getVal()) {
                    root = rr_rotate(root);
                } else {//否则插在左子树的右边满足lr的情况
                    root = rl_rotate(root);
                }
            }
        }

        //3.更新高度
        root.setH(root.getHeight());
        return root;
    }

    /**
     * 1.ll旋转（右旋）
     *
     * @param root
     */
    public static AVLTree ll_rotate(AVLTree root) {
        AVLTree left = root.getLeft();
        root.setLeft(left.getRight());
        left.setRight(root);
        root.setH(root.getHeight());
        left.setH(left.getHeight());
        return left;
    }

    /**
     * 2.lr旋转，先让左子树右孩子左旋形成ll，后按ll方法正常右旋
     *
     * @param root
     */
    public static AVLTree lr_rotate(AVLTree root) {
        //1.先让左子树右孩子左旋形成ll
        AVLTree left = root.getLeft();
        //2.后按ll方法正常右旋
        root.setLeft(rr_rotate(left));
        return ll_rotate(root);
    }

    /**
     * 3.rr旋转（左旋）
     *
     * @param root
     */
    public static AVLTree rr_rotate(AVLTree root) {
        AVLTree right = root.getRight();
        root.setRight(right.getLeft());
        right.setLeft(root);
        root.setH(root.getHeight());
        right.setH(right.getHeight());
        return right;
    }

    /**
     * 4.rl旋转
     *
     * @param root
     */
    public static AVLTree rl_rotate(AVLTree root) {
        AVLTree right = root.getRight();
        root.setRight(ll_rotate(right));
        return rr_rotate(root);
    }

    // 统一使用安全高度获取方法
    public static int safeHeight(AVLTree node) {
        return node != null ? node.getH() : 0;
    }

    /**
     * 中序遍历
     *
     * @param avlTree
     */
    public static void inOrder(AVLTree avlTree) {
        if (avlTree == null) {
            return;
        }
        inOrder(avlTree.getLeft());

        //输出值之外还输出高度（校验是否旋转）
        System.out.println(avlTree.getVal() + " " + avlTree.getHeight());
        inOrder(avlTree.getRight());
    }
}

/**
 * 测试数据：（本数据为特殊的链状结构，读者也可自己设计数据进行测试）
 * 6
 * 1 2 3 4 5 6
 * 3
 * 4
 * 3
 * 2
 * ---------
 * 结果1
 * 1 1
 * 2 2
 * 3 1
 * 4 3
 * 5 2
 * 6 1
 * ---------
 * 结果2
 * 1 1
 * 2 3
 * 5 2
 * 6 1
 * ----------
 * 结果3
 * 1 1
 * 5 2
 * 6 1
 */
